package com.linyaonan.leetcode.medium._142;

import java.util.HashMap;

/**
 * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 *
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
 *
 * 不允许修改 链表。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/linked-list-cycle-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 输入：head = [3,2,0,-4], pos = 1
 * 输出：返回索引为 1 的链表节点
 * 解释：链表中有一个环，其尾部连接到第二个节点。
 *
 * 输入：head = [1,2], pos = 0
 * 输出：返回索引为 0 的链表节点
 * 解释：链表中有一个环，其尾部连接到第一个节点。
 *
 * 输入：head = [1], pos = -1
 * 输出：返回 null
 * 解释：链表中没有环。
 */
public class Solution {

    /**
     * 思路一：最简单的思路就是将所有的节点进行保存，如果成环则会存在哈希表中存在的节点直接return即可
     *
     * 但是该算法有一个比较大的问题就是如果数据长度很大，map就会很大，并且map resize的过程会比较耗时
     *
     * 整体的算法结果：
     *
     * 执行用时：4 ms, 在所有 Java 提交中击败了5.30%的用户
     * 内存消耗：42.4 MB, 在所有 Java 提交中击败了6.25%的用户
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }

        /**
         * 用来记录出现过的节点
         */
        HashMap<ListNode, Boolean> map = new HashMap<>();

        while (head != null) {
            if (map.containsKey(head)) {
                return head;
            } else {
                map.put(head, true);
                head = head.next;
            }
        }

        return null;

    }

    /**
     * 思路二：快慢指针，如果快指针可以与慢指针相遇则表示成环
     * 判断出确实是环形链表后再借助哈希表找出成环位置
     * @param head
     * @return
     */
    public ListNode detectCycle2(ListNode head) {
        if (!isRing(head)) {
            return null;
        }

        /**
         * 用来记录出现过的节点
         */
        HashMap<ListNode, Boolean> map = new HashMap<>();

        while (head != null) {
            if (map.containsKey(head)) {
                return head;
            } else {
                map.put(head, true);
                head = head.next;
            }
        }

        return null;

    }

    /**
     * 思路三：转换为数学问题
     *
     * 前提说明：
     * 1. 如果有环，那么快慢指针一定是在环中相遇的，因为快指针首先进入环，然后就无法出环，那么慢指针进入环后必定会被快指针追上
     * 2. 如果没有环，快指针就会遍历结束
     *
     *
     * 情景重现：
     *
     * 1. 假设head距离环口的距离为a，环的总长度为b，快慢指针在环中相遇的位置距离环口为c，那么可得一下等式
     *
     * 快指针路径 = a + n(b) + c
     * 慢指针路径 = a + c
     *
     * 又因为快指针速度是慢指针的2倍即 a + n(b) + c = 2 (a + c) => n * b = a + c
     *
     * 特性：快慢指针相遇时 n必然等于1
     *
     * 说明如下：
     *
     * 首先假设环的长度为A，慢指针的速度为1，快指针速度为2。快慢指针都在环内，最大的差距为A-1距离，追上A-1距离需要A-1/(2-1)
     * 那么在慢指针走完一圈之前必定相遇
     *
     * 最终 b = a + c
     *
     * 所以慢指针在环内剩余的长度与head走到环口的距离一致，所以当快慢指针相遇时，在使用一个新指针从对头开始移动与慢指针相遇的位置就是环口
     *
     *
     *
     * @param head
     * @return
     */
    public ListNode detectCycle3(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode h = head;
        ListNode l = head;
        ListNode t = head;

        while (h != null && h.next != null) {
            h = h.next.next;
            l = l.next;
            if (h == l) {
                while (l != t) {
                    l = l.next;
                    t = t.next;
                }
                return t;
            }
        }

        return null;

    }

    private boolean isRing(ListNode head) {
        if (head == null) {
            return false;
        }

        ListNode h = head.next;
        ListNode l = head;

        while (h != null && h.next != null) {
            if (h.equals(l)) {
                return true;
            } else {
                h = h.next.next;
                l = l.next;
            }
        }

        return false;
    }
}